package com.base;

import java.util.Arrays;

public class 二分查找 {
    /*
     *推荐固定用这个写法、这个函数
     * arr非递减序，
     * 找出arr中 >=target的数 出现的第一个位置
     * (left,right)是开区间
     */
    public static int lower_bound(int[]arr,int target){
        int left=-1,right=arr.length;
        while (left+1<right){
            int mid=left+(right-left)/2;
            //只有小于时才收左边，所以能保证找到的是第一个target
            if(arr[mid]<target){
                left=mid;
            }else{
                right=mid;
            }
        }
        return right;
    }

    /**
     * 调用库函数
     * 找到第一个出现的位置
     * 存在 返回 正数-》下标
     * 不存在 返回 负数-》如-3 表示应插入第三个位置
     * 如果要找出现的最后一个位置，那就先找到target+1的位置
     */
    public static int lower_bound2(int[]arr,int target){
        return Arrays.binarySearch(arr,target);
    }

    public static void main(String[] args) {
        int[]arr={1,2,3,4,4,4,6,6,6,6,7,8,9};
        System.out.print(lower_bound2(arr,5));
    }
}
